In the field of distribution of materials or goods, one often encounters the situation where certain qualities of the material or goods to be delivered vary from lot to lot, and where different parties receiving the materials or goods may have different requirements for these certain qualities. These qualities are often associated with the price that is charged, such that higher quality goods are generally priced higher than are lower quality goods. In order for a business to maximize its revenue, it must continually ensure that the materials or goods of varying quality are delivered to the right customers for those goods.
The coal mining business is one business in which the problem of maximizing revenue by selection of the quality of coal to be delivered to various customers is especially complex and limited. Referring to FIG. 1, a coal delivery facility is illustrated as an example of this problem. In this exemplary facility, a railroad track 10i is an incoming track along which empty coal trains travel to the facility, and which serves two sets of "bins", or locations at which coal may be loaded. Track 10i splits into a track 10a and a track 10b corresponding to these two groups of bins. In this example, track 10a travels near a series of slots 4.sub.0 through 4.sub.5 in a coal receiving facility 2; each of slots 4.sub.0 through 4.sub.5 have a pile of coal located thereat, from which a train may be loaded through use of plow 6. Plow 6 is a conventional coal loading apparatus that moves coal from the associated pile through the slot 4 into the train. Track 10b, on the other hand travels near silos 8.sub.0 and 8.sub.1, each of which stores a load of coal that may be loaded into a coal train along track 10b. Each bin (i.e,. each of slots 4 and silos 8) stores a full trainload of coal, with a trainload corresponding to approximately 100 boxcars in volume.
In this exemplary coal delivery facility, as is typical for coal delivery facilities, the quality of the coal located at each slot 4 or silo 8 differs from the quality of the coal located at the other bins. For purposes of this example, the quality of coal corresponds to its energy yield (e.g., in BTu/pound) and to the various levels of both contaminants (e.g., sulfur) and desirable chemicals (e.g., sodium). This variation in quality among bins (i.e, among slots 4 and silos 8 of FIG. 1) is due to the differing quality of coal located at different portions of a coal mine, such as an open pit coal mine.
Also as is typical in the business, incoming empty coal trains are generally associated with a particular customer, so that the coal is picked up at the delivery facility of FIG. 1 for delivery at a customer's location. Each customer generally has specific requirements for the energy yield of the coal that it receives. It is typical in the business that a customer will pay premiums at a specified rate if it receives coal having an energy yield above a particular baseline range, and pays at a reduced rate if it receives coal at an energy yield below the baseline range. The schedule of premiums and rebates may be considered as a function of energy yield in the manner illustrated, for three hypothetical examples, in FIG. 2.
In a first premium/penalty function illustrated by plot 12 in FIG. 2, the customer pays at a baseline rate for coal having between 8450 and 8550 BTu/lb, and pays at a premium of 0.04.cent./ton for each BTu/lb above 8550 BTu/lb, up to a maximum premium of 5.cent./ton (achieved at a yield of 8675 BTu/lb); the customer also pays at a reduced rate of 0.02.cent./ton for each BTu/lb below 8450 BTu/lb, down to a minimum yield of 1250 BTu/lb below which the customer will not accept the coal (i.e., the price is zero). By way of example, a second premium/penalty function illustrated by plot 13 has a baseline range (8500 to 8650 BTu/lb) that is shifted from that of the function of plot 12, with different slopes of premium and penalty, and with no maximum premium or minimum yield threshold. A third premium/penalty function is illustrated by plot 14 of FIG. 2, in which the baseline range extends from 8400 to 8600 BTu/lb, and in which the premiums and penalties are 2.cent. step functions over 100 BTU/lb ranges on either side of the baseline range.
The operator of the exemplary coal distribution facility of FIG. 1 of course wishes to maximize the premiums received and to minimize the penalties assessed. As such, the operator will sample the coal located at the various bins for laboratory analysis of its energy yield, as well as its contaminants and desired chemicals, and use this analysis in the assignment of a series of incoming trains to the various bins.
The optimization of income quickly becomes a complex problem, however, especially in the worst case where eight incoming trains are associated with eight different premium/penalty functions, and where the coal in the eight possible bins (slots 4 and silos 8) varies in yield. Consideration of these functions illustrated by plots 12, 13, 14 clearly indicates the problem of maximizing the premiums paid from non-uniform inventory sources, such as the coal facility of FIG. 1, especially since the baseline ranges of the functions can differ from one another, not only in center point (BTU/lb) but also in width, and since the premium and penalty slopes are not the same for each of the functions. Estimation of the optimum loading sequence is therefore not a trivial operation for a human operator.
By way of further background, calculus-based optimization techniques have been applied in the past to the coal mine scheduling problem of FIGS. 1 and 2. According to this technique, also referred to as the "hill-climbing" method, the gradient of a point on the function under analysis is evaluated, and a next point of analysis is selected by moving an incremental distance in a direction indicated by the derivative (i.e., when seeking a maximum, the increment is taken in the direction with the positive gradient). As is well-known in the art, these methods are vulnerable to local extrema which can trap the optimization routine at a point that is not the true maximum for the function. In addition, this technique does not handle functions with infinite derivatives (i.e., at steps in the function). As shown in FIG. 2, step function changes in the premium/penalty function can be quite common. As such, the application of the calculus-based technique to the optimization of the coal delivery facility problem was not successful.
Furthermore, as noted above, the decision process for assigning incoming coal trains to particular slots 4 or silos 8 also involves other factors than the energy yield of the coal inventory. One such factor is the presence of contaminants, such as sulfur, moisture, and ash, for which the coal customers will have maximum values, and will refuse acceptance of coal shipments that exceed these specifications for any of the specified contaminants. Because of different uses and environmental constraints, however, it is common that different coal customers will have different contaminant specifications. The consideration of which incoming coal train is to be assigned to which bin of the coal delivery facility thus further complicates the optimization of revenue.
Another complicating factor in the example of the coal delivery facility of FIG. 1 is the sodium requirement that may be specified by some customers. It is common for coal customers to require that a certain amount of sodium be present in the delivered coal, for purposes of minimizing the buildup of contaminants in their coal burning facilities; this requirement may also vary from customer to customer. If the laboratory analysis indicates that the sodium content of the coal in a particular bin is below the desired level, the coal facility can add a chemical to increase the sodium content; an example of this chemical is commonly referred to in the art as "Trona". Trona is quite costly, however (e.g., on the order of $130/ton), and as such any optimization of revenue should also consider minimizing the use of Trona by assigning incoming trains having less stringent sodium specifications to the lowest sodium bins.
Yet another complicating factor in the optimization routine is the timing of the loading of the incoming trains. Coal carriers typically specify a penalty if the train leaves the coal delivery facility late. In the example of FIG. 1, which is typical of a coal delivery facility, only one train can be loaded from slots 4 at a time, and only one train can be loaded from silos 8 at a time; furthermore, the loading from a slot may take longer (e.g., on the order of three hours) than loading from a silo (e.g., on the order of one hour). Further complicating the timing of this operation is the movement of plow 6 which is used to load coal from a bin 4 to a train, as plow 6 moves quite slowly among slots 4, and also disrupts the coal as it often drags some coal from one slot to another. Consideration of these timing issues in the revenue optimization also greatly complicates the problem.
Indeed, calculus-based optimization techniques such as the hill-climbing technique are generally unable to handle optimization of a function having differing input types (e.g., energy yield vs. contaminant specifications vs. timing penalties), at least without definition of a rigorous differentiable function relating these different input types.
By way of further background, optimization methods known as "genetic algorithms" have been applied to scheduling problems. As is well known in the art, genetic algorithms serve to select a string (referred to as a "chromosome") of digits ("genes") having values ("alleles") that provides the optimum value of a "fitness function". According to this technique, a group of chromosomes ("a generation") is first randomly generated, and the fitness function is evaluated for each chromosome. A probability function is then produced to assign a probability value to each of the chromosomes according to its fitness function value, so that a chromosome with a higher fitness function value obtains a higher probability. A "reproduction pool" of chromosomes is then produced by random selection according to the probability function; the members of this reproduction pool are more likely to be selected from the higher fitness function values. Each chromosome from the reproduction pool then "reproduces" with another, randomly selected, chromosome in the reproduction pool by exchanging genes at a randomly selected "crossover" point in the chromosome; this reproduction results in the second generation of chromosomes. Mutation may be introduced by randomly altering a small fraction of the genes in the second generation (e.g., one in one thousand). The fitness function is then evaluated for each of the chromosomes in the second generation, and the reproduction process is repeated until the desired convergence is obtained.
An example of the use of a genetic algorithm in a scheduling problem is described in U.S. Pat. No. 5,319,781, issued Jun. 7, 1994.
It is therefore an object of the present invention to provide a method of optimizing the distribution of non-uniform inventory in an efficient manner.
It is a further object of the present invention to provide such a method in which the optimization considers functions having infinite gradients.
It is a further object of the present invention to provide such a method in which the optimization considers inputs and effects of inputs of different types.
It is a further object of the present invention to provide such a method in which the distribution of the non-uniform inventory is made according to a sequence of varying requirements.
Other objects and advantages of the present invention will be apparent to those of ordinary skill in the art having reference to the following specification together with its drawings.